package anthology.leet_code_hot;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

//https://leetcode.cn/problems/longest-consecutive-sequence/description/
//给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
//请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
public class _128最长连续序列 {
    //暴力
    class Solution {
        public int longestConsecutive(int[] nums) {
            if(nums.length == 0) return 0;
            if(nums.length == 1) return 1;
            Arrays.sort(nums);
            int ans = 1,sum = 1;
            for(int i=1; i<nums.length; i++){
             if(nums[i]-nums[i-1] == 1)
                 sum++;
             else if(nums[i]-nums[i-1] == 0)
                 continue;
             else
                 sum = 1;
             ans = Math.max(ans,sum);
            }
            return ans;
        }
    }
    //哈希表
    class Solution2 {
        public int longestConsecutive(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for(int num : nums)
                set.add(num);
            int ans = 0;
            for (int num : set){
                if (!set.contains(num-1)){
                    int currentNum = num;
                    int currentStreak = 1;
                    while (set.contains(currentNum+1)){
                        currentNum++;
                        currentStreak++;
                    }
                    ans = Math.max(ans,currentStreak);
                }
            }
            return ans;
        }
    }
}
